package NiuKe.PriorityQueue;

import java.util.Arrays;
import java.util.PriorityQueue;

/*堆的应用：给你100w数据，找到前十个最大的元素。
* 1：整体进行排序，然后输出前10个最大的元素
* 2：利用刚刚学过的堆
* 总结：求前k个最大的元素，建一个小根堆
*      求前k个最小的元素，建一个大根堆*/


//堆在逻辑上是完全二叉树，是用数组实现的
/*利用以下性质
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子*/
public class Heap {
    public  int[] elem;
    public  int usedSize;

    public Heap(){
        this.elem=new int[10];

    }

    /**
     * 向下调整函数的实现-大根堆
     * @param parent 每棵树的根节点
     * @param len 每棵树的调整的结束位置
     */
    public void shiftDown(int parent,int len){
        int child=2*parent+1;
        //1，至少有一个孩子
        while (child < len){
            if (child+1<len && elem[child]<elem[child+1]){
                child++;//保证child是最大的孩子
            }
            if (elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }

        }
    }
    /*建堆的时间复杂度是多少
    * 时间复杂度：每一层节点的个数*每个节点调整的高度*/
    public void createHeap(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            usedSize++;
        }

        for (int i = (usedSize-1-1)/2; i >=0  ; i--) {
            shiftDown(i,usedSize);
        }
    }



    public boolean isFull(){
        return usedSize==elem.length;
    }
    //调整过程
    private void shiftUp(int child){
        int parent=(child-1)/2;
        while (child > 0){
            if (elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    //入队列
    public void offer(int val){
        if (isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++]=val;
        shiftUp(usedSize-1);

    }
    public boolean isEmpty(){
        return usedSize==0;
    }
    public int poll(){
        if (isEmpty()){
            throw new RuntimeException("优先级队列为空");
        }
        int tmp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=tmp;
        usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }
    public void heapSort(){//将堆建立一个升序数组
        for (int i = usedSize-1; i > 0 ; i--) {
            int tmp=elem[0];
            elem[0]=elem[i];
            elem[i]=tmp;
            //交换完成之后调整堆
            shiftDown(0,i);
        }
    }

    public static void main(String[] args) {
        PriorityQueue priorityQueue=new PriorityQueue<>();
        //默认是小堆
        /*每次入堆的时候都必须保证当前是大根堆或小根堆
        * 每次弹出的时候都必须保证当前是大根堆或小根堆*/
        int[] array={27,15,19,18,28,34,65,49,25,37};
        Heap heap=new Heap();
        heap.createHeap(array);
        System.out.println("======================");
        heap.offer(80);
        System.out.println("======================");
        int a=heap.poll();
        System.out.println(a);
        a= heap.poll();
        System.out.println(a);
        heap.heapSort();
        System.out.println("======================");
    }
}
